UVa/10385 - Duathlon/10385.cpp

   1 // Accepted. Ternary search.
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <deque>
  19 #include <stack>
  20 #include <list>
  21 #include <map>
  22 #include <set>
  23
  24 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  26 #define D(x) cout << #x " is " << x << endl
  27
  28 const double eps = 1e-9;
  29
  30 const int MAXN = 20;
  31 double running_speed[MAXN], biking_speed[MAXN];
  32 int n;
  33
  34 double margin(double x, int t) {
  35     double me = x / running_speed[n - 1] + (t - x) / biking_speed[n - 1];
  36     double them = 1e100;
  37     for (int i = 0; i < n - 1; ++i) {
  38         them = min(them,  x / running_speed[i] + (t - x) / biking_speed[i]);
  39     }
  40     assert(them >= 0);
  41     return them - me;
  42 }
  43
  44 double best_running_length(int t) {
  45     double left = 0, right = t;
  46     for (int i = 0; i < 150; ++i) {
  47         double r1 = (2 * left + right) / 3;
  48         double r2 = (left + 2 * right) / 3;
  49         assert(r1 <= r2);
  50         if (margin(r1, t) < margin(r2, t)) {
  51             left = r1;
  52         } else {
  53             right = r2;
  54         }
  55     }
  56     return (left + right) / 2;
  57 }
  58
  59 int main(){
  60     int t;
  61     while (cin >> t) {
  62         cin >> n;
  63         for (int i = 0; i < n; ++i) {
  64             cin >> running_speed[i] >> biking_speed[i];
  65             assert(running_speed[i] > eps and biking_speed[i] > eps);
  66         }
  67
  68         double r = best_running_length(t);
  69         double m = margin(r, t);
  70         if (m < 0.0) {
  71             printf("The cheater cannot win.\n");
  72         } else {
  73             printf("The cheater can win by %.0lf seconds with r = %.2lfkm and k = %.2lfkm.\n",  m * 3600, r, t - r);
  74         }
  75     }
  76     return 0;
  77 }